GJK algoritam
Provjeru sudara dvaju konveksnih omotača vršiti ćemo GJK(Gilbert–Johnson–Keerthi) algoritmom. GJK algoritam nije među zastupljenijim algoritmima u interaktivnim simulacijama. Razlog za to leži u ne baš jasnom postupku implementacije algoritma. Većina radova na ovu temu pristupala je GJK algoritmu sa matematičkog gledišta. Christer Ericson u svojoj knjizi „Real-Time Collision Detection” zagovara vektorski pristup ovom algoritmu. U ovom radu će biti opisan vektorski pristup koji se nastavlja na rad Christera Ericsona, ali donosi bitna poboljšanja, kako u brzini samog algoritma, tako i u jednostavnosti njegove implementacije.
Prije nego pristupimo objašnjenju samog algoritma, moramo definirati neke pojmove iz područja detekcije sudara.
Suma i razlika Minkovskog
Neka su A i B dva skupa točaka i neka su a i b vektori dviju točaka u tim skupovima. Suma Minkovskog je tada data izrazom:
Suma Minkovskog
Razlika Minkovskog je:
Razlika Minkovskog
Voronoieve regije
Za konveksni objekt C, definiramo primitivu P kao vrh, brid ili lice objekta C. Voronoieva regija primitive P konveksnog objekta C je tada skup točaka u prostoru koje su bliže primitivi P nego bilo kojoj drugoj primitivi konveksnog objekta C.
Trokut ima sedam Voronoievih regija. Voronoieve regije vrhova V1, V2 i V3. Voronoieve regije bridova E1, E2 i E3. Voronoieva regija trokuta F.
Funkcija potpore
Često nas za neki konveksni objekt zanima koja je točka tog objekta najudaljenija u nekom smjeru. Smjer u kojem tražimo najudaljeniju točku objekta zovemo vektor potpore i označavamo sa s.
Funkcije potpore trokuta za zadani vektor potpore s jednaka je točki V1.
Funkcija Obradi_simpleks
Funkcija Obradi_simpleks provjerava u kojoj Voronoievoj regiji trenutnog simpleksa se nalazi ishodište te na temelju toga određuje novi simpleks i novi vektor potpore.
Ukoliko se ishodište nalazi unutar simpleksa u obliku trokuta, u dvodimenzionalnom slučaju, ili unutar simpleksa u obliku tetraedra, u trodimenzionalnom slučaju, tada su dva objekta u sudaru
Glavni algoritam
Glavna ideja GJK algoritma je da se pokuša izgraditi simpleks unutar razlike Minkovskog dvaju objekata koji će obuhvatiti ishodište. Ukoliko se u tome uspije, objekti su u sudaru. Ukoliko GJK nije u stanju izgraditi simpleks, ishodište se nalazi izvan razlike Minkovskog i objekti nisu u sudaru. Simpleks koji GJK pokušava izgraditi je u slučaju trodimenzionalnog GJK algoritma tetraedar, a u slučaju dvodimenzionalnog GJK algoritma trokut. Vrhovi simpleksa su uvijek vrhovi konveksnog omotača razlike Minkovskog.
GJK - traženje simpleksa.
a) Želimo izvršiti provjeru sudara dvaju konveksnih objekata A i B. Tijekom provjere sudara, kretati ćemo se po konveksnom omotaču razlike Minkovskog objekata A i B. Samo razliku Minkovskog za ova dva objekta nećemo računati. To nije potrebno ako znamo da će funkcija potpore uvijek vratiti točku na konveksnom omotaču razlike Minkovskog.
b) Prije same petlje GJK algoritma, moramo izvršiti inicijalizaciju simpleksa S i vektora potpore s. Za početnu točku možemo uzeti bilo koju točku na konveksnom omotaču razlike Minkovskog. Vektor potpore s se inicijalizira na negativnu vrijednost početne točke. Početnu točku dodajemo u simpleks i započinjemo glavnu petlju GJK algoritma.
c) Funkcija potpore je vratila novu točku. Ukoliko vrijedi A s < 0, prekidamo s izvođenjem algoritma jer sudar ne postoji.
d) Funkcija Obradi_simpleks je u prošloj iteraciji vratila nepromijenjeni simpleks i novi vektor potpore. Simpleks nije mijenjan jer se ishodište nalazi u Voronoievoj regiji linije koja tvori postojeći simpleks. Nakon što je funkcija potpore vratila novu točku koja je udaljenija od ishodišta za ovaj vektor potpore, novu točku dodajemo u simpleks i ponovno pozivamo funkciju Obradi_simpleks.
e) Funkcija Obradi_simpleks je u prošloj iteraciji vratila samo dvije točke. Razlog za to je što se ishodište nalazi u Voronoievoj regiji linije koja tvori trenutni simpleks. Funkcija potpore vrača novu točku koja je udaljenija od ishodišta te ju dodajemo u strukturu simpleks koja je sada ponovno trokut.
f) Funkcija Obradi_simpleks javlja da su objekti A i B u sudaru jer se ishodište nalazi unutar trenutnog simpleksa. Glavni GJK algoritam ovime završava.